/*
1606. 找到处理最多请求的服务器
https://leetcode.cn/problems/find-servers-that-handled-most-number-of-requests/description/
*/
class Solution {
private:
    using P = pair<int, int>;
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        int maxNum = 0;
        int num[k];
        memset(num, 0, sizeof(num));
        // 可用服务器的集合，默认是按照编号升序排列
        set<int> avails;
        for (int i = 0; i < k; ++i)
        {
            avails.insert(i);
        }
        // 结束时间的小顶堆的优先级队列 first是结束时间 second是编号
        priority_queue<P, vector<P>, greater<P>> q;

        for (int i = 0;  i < arrival.size(); ++i)
        {
            int t = arrival[i];
            // 先把队列里已完成的弹出
            while (!q.empty() && q.top().first <= t)
            {
                avails.insert(q.top().second);
                q.pop();
            }
            // 没有可用，直接忽略
            if (avails.size() == 0)
            {
                continue;
            }

            int curr = *avails.begin();
            // 二分找到可用的值
            auto iter = avails.lower_bound(i % k);
            if (iter != avails.end())
            {
                curr = *iter;
            }
            q.push({{t + load[i]}, curr});
            avails.erase(curr);
            ++num[curr];
            maxNum = max(maxNum, num[curr]);
        }


        // 再次遍历取出最大次数对应的服务器
        vector<int> res;
        for (int i = 0; i < k; ++i){
            if (num[i] == maxNum){
                res.push_back(i);
            }
        }
        return res;
    }
};
